% !Mode:: "TeX:UTF-8"
\chapter{情绪传播模型}

\section{引言}

在影响最大化问题中，信息传播模型用于对网络中的信息扩散规则进行建模。影响最大化算法在找到种子节点集合之后，模拟信息从种子节点集合出发并基于给定信息传播模型的扩散过程。该过程结束后信息的传播范围即为种子节点集合的传播范围，从而用于评估影响最大化算法的优劣。因此，影响最大化算法中使用的信息传播模型需要尽可能地贴切现实网络的信息传播过程。

当前，大部分影响最大化算法的研究都是基于独立传播模型和线性阈值模型。根据\ref{sec2.3.1}节中独立传播模型的描述可以发现，独立传播模型有如下两点不足：
\begin{enumerate}
\item 在相同的用户之间，不同信息的传播概率是一样的。
\item 信息传播没有考虑到信息本身的因素。
\end{enumerate} 

事实上在社交网络中，不同信息在相同用户之间传播概率应当是不一样的。在社交网络中，一些用户偏向于向别人传播负面情绪，而另一些用户偏向于向别人传播正面情绪。一条包含大量愤怒情绪的信息和一条包含大量高兴情绪的信息，在社交网络中的传播范围和影响的用户显然是不相同的。

本文认为，用户发布的一条信息中包含了多种用户的情绪，信息是情绪的载体，信息的传播本质上是用户情绪的传播。基于上述假设，我们提出了在线社交网络的情绪传播模型。在该模型中，每条信息是五种情绪的组合，包括愤怒、厌恶、高兴、低落和恐惧，且不同的情绪在相同用户之间有不同的传播概率。信息在用户之间的传播概率为情绪在用户之间传播概率的加权组合。

在本章中，我们将首先介绍情绪传播模型的定义，并类比独立传播模型的参数估计方法给出情绪传播模型的参数估计。本章在微博数据集上进行了实验，实验结果表明情绪传播模型要优于独立传播模型。

\section{情绪传播模型定义}
如图\ref{fig-text-emo}所示，对于每一条信息$i$，我们可以将其看成是五种情绪的组合。$\gamma_i^c=P(C=c|i)$表示情绪$c$关于信息$i$的权重，且$\Sigma_{c=1}^5\gamma_i^c=1$。这里，$\gamma_i^c$可以由训练好的情感分类器得到。

\begin{figure}[h!]{}
\centering
\includegraphics[width=0.7\textwidth]{figure/chap3/text_emotions.png}
\caption{文本的情绪组合示意图}
\label{fig-text-emo}
\end{figure}

情绪以一定的概率在用户之间传播，即对于一种情绪$c$和边$(v, u)$，$p_{v,u}^c$表示情绪$c$从节点$v$传播到节点$u$的概率。

图\ref{fig-mic-demo}是一个情绪传播模型的简要示意图，如图所示每条边的信息传播概率是五种情绪传播概率的加权组合。因此，一条信息$i$在用户$v$和$u$之间的传播概率就可以写为:
\begin{equation}
\label{mic_edge_prob}
p_{v,u}^i = \Sigma_{c=1}^5{\gamma_i^c p_{v,u}^c}
\end{equation}

\begin{figure}[h!]{}
\centering
\includegraphics[width=0.7\textwidth]{figure/chap3/mic_demo.png}
\caption{情绪传播模型示意图}
\label{fig-mic-demo}
\end{figure}

因此在情绪传播模型中，从初始节点$v$出发信息$i=\{\gamma_i^0, \gamma_i^1, \gamma_i^2, \gamma_i^3, \gamma_i^4\}$在网络中传播过程如下：对于每一个节点$v$的邻居$u$，$v$都有唯一一次机会它，且激活的概率$p$由信息$i$和边$(v,u)$中每种情绪的传播概率共同决定，即$p = \Sigma_{c=1}^5{\gamma_i^c p_{v,u}^c}$。被$v$激活的节点同样获得一次激活其邻居的机会，依次类推。当没有更多的节点被激活时，信息传播过程停止。

\section{参数估计}

在情绪传播模型中有两类参数，一类是信息的情绪分布，另一类是边的情绪传播概率。其中信息的情绪分布可以由训练好的情感分类器得到，而边的情绪传播概率则需要根据现实网络中的信息传播过程估计得到。

\subsection{独立传播模型参数估计}

在给出情绪传播模型的参数估计之前，我们先介绍独立传播模型的参数估计方法。

根据\cite{saito_prediction_2008}中的定义，令$D(0)$表示在$t=0$时刻初始化为激活状态的节点集合，$D(t)$表示在$t$时刻新激活的节点集合。则，一个完整的信息传播过程可以写为$D = D(0) \cup D(1) \cup D(2) \dots \cup D(t)$。

为了更好地解释如何从实际数据中估计独立传播模型的参数，我们定义$F_{u}^+$表示可能激活$u$的邻居节点集合，即：
$$F_u^+ = \{v|(v,u)\in E, t_u - t_v = 1\}$$

类似地，定义$F_{u}^-$表示肯定没有激活$u$的邻居节点集合，即：
$$F_u^- = \{v|(v,u)\in E, t_u - t_v > 1\}.$$

其中，$t_u$表示$u$第一次处于激活状态的时间，若$u$没有被激活，则$t_u=\infty$。

根据\cite{dempster_maximum_1977}中提出的计算完全数据集似然函数的方法，以$\theta=\{p_{v,u}\}$为参数我们可以定义传播过程$D$的似然函数为：
$$L(\theta;D) = \prod_{u}{P_u^+P_u^-},$$
{}{}
其中，
\begin{equation}
\label{p_influence}
P_u^+ = 1 - \prod_{v\in F_u^+}{(1 - p_{v, u})}
\end{equation}
且$$P_u^- = \begin{cases}\prod_{v\in F_u^-}{(1-p_{v,u})}, & if F_u^- \ne \emptyset \cr 1, &otherwise\end{cases}.$$
令$\{D_s: s = 1, 2 \dots, S\}$表示$S$个相互独立的信息传播过程的集合，则以$\theta$为参数的对数似然函数可以写为：
\begin{equation}
\label{likelihood_all_episode}
L(\theta)=\Sigma_{s=1}^S{logL(\theta;D_s)}.
\end{equation}

一般来说，解决该问题的方法为计算$L(\theta)$关于$\theta$的导数并计算出解析解。然而，要求$L(\theta)$的导数并不容易，\cite{saito_prediction_2008}给出了一个期望最大化算法。假设$u$是当前新激活的节点，那么对于$F_u^+$中的一个节点$v$成功激活$u$的概率为$\hat{p}_{v,u} / \hat{P}_u^+$，没有成功激活$u$的概率为$1 - \hat{p}_{v,u} / \hat{P}_u^+$。注意，$\hat{p}_{v,u}$是当前$p_{v,u}$的估计值，$\hat{P}_u^+$可以通过公式\ref{p_influence}计算得到。因此，我们可以写出该问题在期望最大化中的Q-函数：
\begin{equation}
\begin{split}
    Q(\theta|\hat{\theta}) = \Sigma_s \Sigma_u\Bigg\lbrace & \Sigma_{v\in F_u^{+,(s)}}\Bigg\lbrace\frac{\hat{p_{v,u}}}{\hat{p_u^{+, (s)}}} \log{p_{v,u}} + 
 (1 - \frac{\hat{p}_{v,u}}{\hat{p}_u^{+,(s)}})\log({1 - p_{v,u}}) \Bigg\rbrace \\ &+ \Sigma_{v\in F_u^{-,(s)}}{\log({1-p_{v,u}})} \Bigg\rbrace.                     
\end{split}
\end{equation}

为了最大化Q-函数，我们需要计算使得$\partial Q / \partial p_{v,u}=0$的$p_{v,u}$取值，计算结果如下：
\begin{equation}
\label{equa:p_v_u}
p_{v, u} = \frac{1}{|S_{v, u}^+|+|S_{v,u}^-|}\Sigma_{s\in S_{v,u}^+}{\frac{\hat{p}_{v,u}}{\hat{P}_u^{+,(s)}}}
\end{equation}

其中，$S_{v,u}^+$表示信息传播过程的集合，该集合中的每个信息传播过程$D_s$都满足$v \in D_s(t)$且$u \in D_s(t+1)$，即：
$$S_{v, u}^+=\{s|v\in F_u^{+,(s)}\}$$
$S_{v,u}^-$表示信息传播过程的集合，该集合中的每个信息传播过程$D_s$都满足$v \in D_s(t)$且$u \notin D_s(t+1)$，即：
$$S_{v,u}^-=\{s|v\in F_u^{-,(s)}\}$$

因此，我们可以总结期望最大化算法的E-步和M-步如下：
\begin{enumerate}
\item E-步：计算每个节点$u$在每个信息传播过程$s$中被激活成功的概率$\hat{P}_u^{+,(s)}$
\item M-步：根据公式\ref{equa:p_v_u}更新$p_{v,u}$的值
\end{enumerate} 

最后，独立传播模型的参数估计算法流程见算法\ref{alg:em_ic}。

\begin{algorithm}[t]
\caption{独立传播模型的参数估计} 
\label{alg:em_ic} 
\begin{algorithmic} 
\STATE 输入：社交网络$G=(V, E)$, 信息传播过程集合$D$
\STATE 输出：参数$\theta=\{p_{v,u}\}$
\STATE 初始化：对于每一个$v$和$u$，$p_{v, u}=0$
\REPEAT  
\FORALL {$u \in V$}
\FORALL {$s \in D$}
\STATE  $\hat{P}_u^{+,(s)} = 1 - \prod_{v\in F_u^{+,(s)}}{(1 - p_{v, u})}$
\ENDFOR
\ENDFOR
\FORALL{$(v, u)\in E$}
\STATE $p_{v, u} = \frac{1}{|S_{v, u}^+|+|S_{v,u}^-|}\Sigma_{s\in S_{v,u}^+}{\frac{\hat{p}_{v,u}}{\hat{P}_u^{+,(s)}}}$
\STATE 其中，$S_{v, u}^+=\{s|v\in F_u^{+,(s)}\}$, $S_{v,u}^-=\{s|v\in F_u^{-,(s)}\}$
\ENDFOR
\UNTIL{convergence} 
\end{algorithmic} 
\end{algorithm}

\subsection{情绪传播模型参数估计}

\subsubsection{信息的情绪分布}

在社交网络中一条信息通常对应一个文本，信息的情绪分布即为文本的情绪分布。之前提到，文本情感分类主要有三种方法，包括基于词典的方法、机器学习的方法和深度学习的方法。基于词典的方法准确率不高，且无法获得情绪的概率值。基于深度学习的方法需要庞大的神经网络模型，且效果没有提升太多。因此，本文使用简单有效的朴素贝叶斯分类器将文本映射为情绪的分布。

朴素贝叶斯是一个生成模型，它通过训练数据集学习联合概率分布。具体地，给定训练数据集$T=\{(d_1, y_1), (d_2, y_2), \dots, (d_3, y_3)\}$，其中$d_i$表示第$i$个文本，$y_i$表示第$i$个文本的情绪类别。朴素贝叶斯学习以下先验概率分布和条件概率分布。先验概率分布：
$$P(c_k),\ k=1,2,\dots,K$$
条件概率分布：
$$P(d_i|c_k)=P(w_i^{(1)}, \dots, w_i^{(n)}|c_k),\ k=1,2,\dots,K$$
其中$w_i^{(j)}$表示文本$i$中的第j个词，K为类别的个数。朴素贝叶斯对条件概率分布作了独立性的假设，即假设文本中的各个词之间是条件独立的。根据条件独立性假设，条件概率分布可以写为：
$$P(d_i|c_k)=P(w_i^{(1)}, \dots, w_i^{(n)}|c_k)=\prod_{j=1}^{n}P(w_i^{(j)}|c_k)$$

朴素贝叶斯模型在进行分类时候，对于一个文本$d$，它属于类别$c_k$的后验概率为：
$$P(c_k|d)=\frac{P(d|c_k)P(c_k)}{\Sigma_kP(d|c_k)P(c_k)}=\frac{P(c_k)\prod_jP(w^{(j)}|c_k)}{\Sigma_kP(c_k)\prod_jP(w^{(j)}|c_k)}$$

朴素贝叶斯模型可以用极大似然估计法估计其参数。先验概率$P(c_k)$的极大似然估计是：
$$P(c_k)=\frac{\sum_{i=1}^{N}I(y_i=c_k)}{N},\ k=1,2,\dots,K$$

每个词$w_j$条件概率为：
$$P(w_j|c_k)=\frac{\sum_{i=1}^{N}I(w_j, y_i=c_k)}{\sum_{i=1}^{N}I(y_i=c_k)}, j=1,2,\dots,n;\ k=1,2,\dots,K$$

式中，$n$为所有文本中不同词的个数，$I$为指示函数。

最后，对于一条信息i，其情绪分布${\gamma_i^{c}}$可以由下式计算得到：
$$\gamma_i^{c}=P(c|d_i)=\frac{P(c)\prod_jP(w^{(j)}|c)}{\Sigma_kP(c)\prod_jP(w^{(j)}|c)}$$

\subsubsection{边的情绪传播概率}

类似于独立传播模型，定义$F_{i,u}^+$表示可能通过信息$i$激活$u$的邻居节点集合，即：
$$F_{i,u}^+ = \{v|(v,u) \in E, t_i(u) - t_i(v) = 1\}$$

同样地，定义$F_{i,u}^-$表示肯定没有通过信息$i$激活$u$的邻居节点集合，即：
$$F_{i,u}^- = \{v|(v,u) \in E, t_i(u) - t_i(v) > 1\}$$

其中$t_i(u)$表示节点$u$接受信息$i$的时间点，若$u$没有接受信息$i$，则$t_i(u)=\infty$。

情绪传播模型和独立传播模型的主要不同是，在独立传播模型中，每一条信息$i$在用户之间的传播概率$p_{v,u}^i$是相同的。而在情绪传播模型中，
信息在用户之间的传播概率是不同情绪$c$在用户之间传播概率$p_{v,u}^c$的加权组合，即$p_{v,u}^i = \Sigma_{c=1}^5{\gamma_i^c p_{v,u}^c}$。
其中${\gamma_i^c}$可以通过上述朴素贝叶斯分类器得到，因此我们要学习的参数为$p_{v,u}^c$。

信息传播过程$D_i$的似然函数关于情绪$c$的分量可以定义为：$$P(D_i|c;\theta)=\prod_u{P_{u,+}^{i,c}P_{u,-}^{i,c}}$$
其中，$$P_{u,+}^{i,c}=1 - \prod_{v \in F_{i,u}^+}{(1-p_{v,u}^c)}$$
且，$$P_{u,-}^{i,c} = \begin{cases}\prod_{v\in F_{i,u}^-}{(1-p_{v,u}^c)}, & if F_{i,u}^- \ne \emptyset \cr 1, &otherwise\end{cases}$$

因此，该问题的Q-函数可以近似为不同情绪分量的加权组合，即：
\begin{equation}
\begin{split}
\label{mic_q_func}
& Q(\theta|\hat{\theta}) = \Sigma_i\Sigma_{c=1}^K \gamma_i^c\Bigg\{\log \pi_{c} + \Sigma_u \\
& \Bigg\{\Sigma_{v\in F_{i,u}^+} \{R_c^i(u,v;\hat{\theta})\log p_{v,u}^c + (1-R_c^i(u,v;\hat{\theta}))\log(1-p_{v,u}^c) \\ 
& + \Sigma_{v\in F_{i,u}^-\log(1-p_{v,u}^c)}\Bigg\}\Bigg\},
\end{split}
\end{equation}

其中，$R_c^i(u,v;\hat{\theta}) = \frac{p_{v,u}^c}{p_{u,+}^{i,c}}$表示$v$通过情绪$c$成功激活$u$的概率，$\pi_c$表示任意一条信息关于情绪$c$的先验概率。

为了最大化Q-函数，我们需要计算使得$\partial Q / \partial p_{v,u}^c=0$的$p_{v,u}^c$取值，计算结果如下：
\begin{equation}
\label{equa:mic_pvu}
p_{v,u}^c=\frac{1}{K_{v,u,c}^+ + K_{v,u,c}^-}\Sigma_{i\in S_{v,u}^+}\gamma_i^c R_c^i(u,v;\hat{\theta})
\end{equation}

其中，$S_{v,u}^+$表示成功从$v$传播给$u$的所有信息的集合，即：
$$S_{v,u}^+=\{i|v \in F_{i,u}^+\}$$
同样，$S_{v,u}^-$表示没有成功从$v$传播给$u$的所有信息的集合，即
$$S_{v,u}^-=\{i|v \in F_{i, u}^-\}$$
$k_{v,u,c}^+=\Sigma_{i\in S_{v,u}^+}\gamma_i^c$且$k_{v,u,c}^-=\Sigma_{i\in S_{v,u}^-}\gamma_i^c$

因此，我们可以总结期望最大化算法的E-步和M-步如下：
\begin{enumerate}
\item E-步：计算每个信息$i$的情绪分量$c$通过节点$v$成功传播给$u$的概率$R_c^i{(u, v;\hat \theta)}$
\item M-步：根据公式\ref{equa:mic_pvu}更新$p_{v,u}^c$的值
\end{enumerate} 

最后，情绪传播模型的参数估计算法流程见算法\ref{alg:em_mic}。

\begin{algorithm}[t] 
\caption{情绪传播模型的参数估计}
\label{alg:em_mic} 
\begin{algorithmic} 
\STATE 输入：社交网络$G=(V, E)$，信息传播过程集合$D$
\STATE 输出：参数$\theta=\{p_{v,u}^c\}$
\STATE 初始化：对于每一个$v$，$u$和$c$，$p_{v, u}^c=0$
\STATE 通过训练好的情感分类器计算$\{\gamma_i^c\}$
\REPEAT 
\FORALL{$c=\{1,\dots,5\}$}
\STATE $\pi_c = \frac{1}{|I|}\Sigma_{i\in I}\gamma_i^c$
\ENDFOR
\FORALL{ $i \in I$}
\FORALL{$c=\{1,\dots,5\}$}
\FORALL {$(u,v)\in E$}
\STATE $R_c^i(u,v;\hat{\theta}) = \frac{p_{v,u}^c}{p_{u,+}^{i,c}}$
\ENDFOR
\ENDFOR
\ENDFOR
\FORALL{ $c=\{1,\dots,5\}$}
\FORALL {$(u,v)\in E: S_{v,u}^+ \not= \emptyset$}
\STATE $p_{v,u}^c=\frac{1}{K_{v,u,c}^+ + K_{v,u,c}^-}\Sigma_{i\in S_{v,u}^+}\gamma_i^c R_c^i(u,v;\hat{\theta})$
\STATE where, $k_{v,u,c}^+=\Sigma_{i\in S_{v,u}^+}\gamma_i^c$ and $k_{v,u,c}^-=\Sigma_{i\in S_{v,u}^-}\gamma_i^c$
\ENDFOR
\ENDFOR
\UNTIL{convergence} 
\end{algorithmic} 
\end{algorithm}

\section{实验设置}
\subsection{实验数据集}
新浪微博代表了中文最受欢迎的社交网站，在新浪微博中，用户可以关注另一个用户或被另一个用户关注。用户可以发布原创微博或者转发其他用户的微博。我们从新浪微博中爬取了88532个用户以及8174702个用户关注关系，爬取的方式为从随机一个用户出发，爬取其关注的所有用户，接着爬取被关注用户关注的用户，以此类推。接下来，我们爬取了这些用户发布的微博，包括原创微博和转发微博，一共2138219条。这样，我们就搜集到了用户发布微博的集合$D=(User, Item, Time)$，$D$中的每条记录表示一个用户（$User$）在某一时刻（$Time$）发布了一条微博（$Item$），我们称一条记录为一个动作（即发布微博的动作）。图\ref{fig:actions}是一些动作的例子，第一列表示新浪微博用户ID，第二列表示微博ID，第三列表示Unix时间戳。因此，图中第一条动作表示ID为1495615684的用户，在1270999521时间戳发布（或转发）了一条ID为100063014的微博。此外，如果用户$u$在时刻$t$发布了一条微博$i$，且用户$v$在$t$时刻之后转发了微博$i$，那么我们称微博$i$从用户$u$传播给了用户$v$。例如在图\ref{fig:actions}，我们认为ID为10012410146的微博从用户1596329427传播给了用户1746572895。

\begin{figure}[h!]{}
\centering
\includegraphics[width=0.5\textwidth]{figure/chap3/actions.png}
\caption{用户发布微博动作示例}
\label{fig:actions}
\end{figure}

为了获取到一个更为可靠动作集合，我们通过以下步骤对收集到的动作进行预处理：
\begin{enumerate}
\item 考虑到随机出现的数据可能会对实验产生干扰，我们过滤掉出现次数小于20次的用户和微博。
\item 如果同一个用户多次发布或转发同一条微博，我们仅保留该用户第一次转发微博的动作。如\ref{fig:actions}中的第1、2个动作。
\item 如果一个用户转发了一条微博，但是该用户没有关注微博的发布者，那么我们舍弃该动作，因为该动作对我们估计边的参数没有任何作用。
\item 由于我们的模型首先需要对微博进行情感分类，因此我们过滤掉那些太短的或者无法进行情感分类的微博。
\end{enumerate} 

经过上述数据清洗之后，最终的用户网络包含11007个用户和70308个关注关系，且留下20136个动作和6383条微博。

为了训练和评估我们的模型，我们将20136个动作按其微博ID随机分成两部分，一部分用来训练，另一部分用来测试。其中，训练数据包含77175个动作，测试数据包含20136个动作。训练和测试数据的具体细节见表\ref{tab-weibo-train-test}。

\begin{table}
    \centering
    \caption{微博训练和测试数据细节}
    \label{tab-weibo-train-test}
    \begin{tabular}{lcr}
    \toprule
     & 训练数据 & 测试数据 \\
    \midrule 
    用户个数 & 10515 & 6997 \\
    边的个数 & 56090 & 24890 \\
    微博个数 & 5100 & 1283 \\
    动作个数 & 77175 & 20136 \\
    \bottomrule
    \end{tabular}
\end{table}

\subsection{实验方法}

在情绪传播模型的实验中，我们首先需要对收集到的微博进行情感分类，得到每条微博包含五种情绪的权重，这五种情绪包括愤怒、厌恶、低落、高兴和恐惧。

在使用朴素贝叶斯模型进行微博情感分类时，我们首先要得到每条微博的标注信息。我们采用\cite{zhao_moodlens:_2012}中所使用的情绪标注方法，该方法将微博中的所有表情符分成四类，并将不同的表情符映射到四种不同的情绪。于是，一条包含表情符的微博就被标注为相应的情绪类别。在该方法的基础上，我们加入恐惧情绪将情绪类别拓展到五类。由于仅根据表情来对微博数据做标注时，得到的恐惧类别的微博数量十分有限，为了均衡训练样本中各个类别的数量，我们手工采集了一些与恐惧相关的关键词。如果微博包含恐惧相关的关键词，就将其标注为恐惧类别。

我们使用微博API采集微博文本数据，并经过一些简单的数据过滤，包括过滤网址和乱码，得到超过400万条微博作为训练数据。我们用该数据集作为训练数据估计朴素贝叶斯模型的参数，并得到一个分类准确率约63.46\%的情感分类器。

实验中在计算每条微博的情绪分布时，我们先使用Jieba分词工具对微博进行分词。对于一个词$w_i$，该词关于情感类别$c_j$的先验概率为:
$$p(w_i|c_j)=\frac{n^{c_j}(w_i)+1}{\Sigma_q(n^{c_j}(w_q)+1)}$$
其中$n^{c_j}(w_i)$表示词$w_i$在标记为$c_j$类别的微博中出现的次数。那么，对于一条由$\{w_i\}$组成的微博，其属于情感类别$c_j$的概率为：
$$p(C=c_j|t)=p(c_j)\prod p(w_i|c_j)$$
在得到微博属于每一个情感类别的概率之后，我们将其进行归一化，使得$\sum_{j=1}^{j=5}{p(c=c_j|t)}=1$。最后，每条微博可以看作是情绪的分布，不同情绪的权重对应不同的概率值。

得到了每条微博的情绪分布之后，我们根据算法\ref{alg:em_mic}的步骤，训练每条边关于不同情绪的参数。

\subsection{实验对比方法}

\subsubsection{独立传播模型}

情绪传播模型是基于独立传播模型提出的，因此将独立传播模型作为一个基线。如算法\ref{alg:em_ic}所示，在独立传播模型中，每条边的概率值只有一个。我们将同样的训练数据和测试数据用于独立传播模型，使用期望最大化算法估计独立传播模型中边的传播概率。

\subsubsection{基于话题的传播模型}

除了与独立传播模型对比外，本文还与\cite{Barbieri2013}中提出的话题传播模型进行对比。话题传播模型在传统的独立传播模型中考虑信息话题对传播的影响，并将每条信息所携带的话题$z$作为参数，连同边的传播概率一起训练。

这里我们直接给出话题传播模型的Q-函数：
\begin{equation}
\begin{split}
\label{tic_q_func}
& Q(\theta|\hat{\theta}) = \Sigma_i\Sigma_{z=1}^K Q_i(z;\hat{\theta})\Bigg\{\log \pi_{z} + \Sigma_u \\
& \Bigg\{\Sigma_{v\in F_{i,u}^+} \{R_z^i(u,v;\hat{\theta})\log p_{v,u}^z + (1-R_z^i(u,v;\hat{\theta}))\log(1-p_{v,u}^z) \\ 
& + \Sigma_{v\in F_{i,u}^-\log(1-p_{v,u}^z)}\Bigg\}\Bigg\},
\end{split}
\end{equation}

话题传播模型的训练算法见算法\ref{alg:em_tic}。

\begin{algorithm}[t]
\caption{EM inference of parameters for TIC} 
\label{alg:em_tic} 
\begin{algorithmic} 
\STATE Input: Social graph $G=(V, E)$, eposides $D$, and $K\in N^+$
\STATE Output: parameters $\theta=\{p_{v,u}^z\}\cup\{\pi_z\}\cup\{\gamma_i^z\}$
\STATE Init $\{p_{v, u}^z\}$ and $\{\pi_z\}$
\REPEAT  
\FORALL{ $i \in I$}
\FORALL{$z=\{1,\dots,K\}$}
\STATE $Q_i(z;\hat{\theta}) = \frac{P(D_i|z;\hat{\theta})\pi_z}{\Sigma_{\tilde{z}}P(d_i|\tilde{z};\hat{\theta})\pi_{\tilde{z}}}$
\FORALL {$(u,v)\in E$}
\STATE $R_z^i(u,v;\hat{\theta}) = \frac{p_{v,u}^z}{p_{u,+}^{i,z}}$
\ENDFOR
\ENDFOR
\ENDFOR
\FORALL{ $z=\{1,\dots,K\}$}
\STATE $\pi_z = \frac{1}{|I|}\Sigma_{i\in I}Q_i(z;\hat{\theta})$
\FORALL {$(u,v)\in E: S_{v,u}^+ \not= \emptyset$}
\STATE $p_{v,u}^z=\frac{1}{K_{v,u,z}^+ + K_{v,u,z}^-}\Sigma_{i\in S_{v,u}^+}Q_i(z;\hat{\theta})R_z^i(u,v;\hat{\theta})$
\STATE where, $k_{v,u,z}^+=\Sigma_{i\in S_{v,u}^+}Q_i(z;\hat{\theta})$ and $k_{v,u,z}^-=\Sigma_{i\in S_{v,u}^-}Q_i(z;\hat{\theta})$
\ENDFOR
\ENDFOR
\UNTIL{convergence} 
\end{algorithmic} 
\end{algorithm}

话题传播模型需要用户指定话题个数，在实验中为了与情绪传播模型进行对比，我们设置话题个数为5，即与情感类别个数相同。

与独立传播模型类似，我们将同样的训练数据和测试数据用于话题传播模型，使用期望最大化算法估计话题传播模型中边的传播概率。

\subsection{实验结果与分析}

\subsubsection{实验结果}

在分别对独立传播模型、话题传播模型和情绪传播模型进行200轮的训练之后，我们得到了每种模型对应边的概率值，见图\ref{fig:ic_edge_probs}、\ref{fig:tic_edge_probs}和\ref{fig:mic_edge_probs}。我们发现，无论是独立传播模型、话题传播模型还是情绪传播模型，大部分边的概率都集中在
大概率（接近1）和小概率（接近0）的范围内。该现象可能是由于训练数据中微博转发路径的不足导致的。我们知道，三种模型都是使用期望最大化算法估计边的参数，在微博转发路径出现多次的边倾向于有较大的概率值，而在转发路径中出现次数较少的边倾向于有较小的概率值。因此微博转发路径的不足容易使得较小概率值的边个数较多。

注意在图中我们只画出了概率大于0的边分布，边概率等于0意味着相应的信息传播模型无法学习出其概率，我们称其为缺失边。如下表\ref{tab-missing-edge}所示，独立传播模型的缺失边占比最大，情绪传播模型的缺失边占比最小。这意味着情绪传播模型可以学习出的边概率个数大于独立传播模型和话题传播模型，即该模型对训练数据的利用效率和拟合能力更强。

事实上，缺失边可能会引起许多问题。例如它导致信息传播模型的不完整从而使模型拟合信息实际传播过程的能力变弱。更严重的是，如果种子节点周围的边概率都缺失了，那么信息无法从该节点传播出去，导致无法模拟信息的传播过程。注意到，虽然情绪传播模型缺失边的比例相比另外两个模型已经达到最优，但是仍然占有接近1/3的比例。因此，我们提出了一个优化的方法来估计情绪传播模型中缺失边的概率。该方法基于以下直觉：如果一个用户经常通过某种情绪来影响某些用户，那么他更可能通过同一种情绪去影响另一些用户。举例来说，微博中的段子手更容易通过其发布微博的高兴情绪来影响其他用户，那么其新粉丝更有可能转发他发布的高兴情绪权重高的微博。基于这种假设，给定一个用户$v$和一种情绪$c$，我们对所有$v$指向的邻居中，边概率$p_{v,u}^c>0$的值求平均，然后将该平均值作用于所有$v$关于情绪$c$的边概率值为0的邻居。具体来说，给定用户$v$和情绪$c$，$F(v)$表示$v$的邻居中关于情绪$c$的边概率大于0的节点集合。那么对于$v$的邻居$u$，如果$p_{v,u}^c=0$，则：
$$p_{v,u}^c = \frac{1}{|F(v)|}\sum_{w \in F(v)}p_{v,w}^c$$

该方法对缺失边的概率值进行优化，我们称之为优化情绪传播模型，该模型的边概率分布见图\ref{fig:emic_edge_probs}。在优化情绪传播模型中，缺失边的占比进一步减小，达到1.41\%。

\begin{figure}[h!]{}
    \centering
    \begin{tabular}{cc}
        \subfigure[独立传播模型边概率分布]{
        	\label{fig:ic_edge_probs}
            \includegraphics[width=.5\textwidth]{figure/chap3/weibo_ic_probs_2.png}
        } \hspace{0em} &
        \subfigure[话题传播模型边概率分布]{
        	\label{fig:tic_edge_probs}
            \includegraphics[width=.5\textwidth]{figure/chap3/weibo_tic_5_probs_2.png}
        } \\
        \subfigure[情绪传播模型边概率分布]{
        	\label{fig:mic_edge_probs}
            \includegraphics[width=.5\textwidth]{figure/chap3/weibo_mic_5_probs_2.png}
        } \hspace{0em} &
        \subfigure[优化情绪传播模型边概率分布]{
        	\label{fig:emic_edge_probs}
            \includegraphics[width=.5\textwidth]{figure/chap3/weibo_mic_5_add_lost_edge_probs_2.png}
        } \\
    \end{tabular}
    \caption{不同信息传播模型边的概率分布图}
    \label{fig-edge-probs}
\end{figure}


\begin{table}
    \centering
    \caption{各模型缺失边占比}
    \label{tab-missing-edge}
    \begin{tabular}{cc}
    \toprule
    模型 & 缺失边比例 \\
    \midrule 
    独立传播模型 & 87.24\% \\
    话题传播模型 & 75.18\% \\
    情绪传播模型 & 28.72\% \\
    \bottomrule
    \end{tabular}
\end{table}

\subsubsection{结果评估}

在训练集上训练得到每个模型的边传播概率之后，我们需要评估每个模型在测试集上的表现。对于每个模型，我们模拟信息传播过程并与测试集上真实的传播过程作对比。具体地，对于测试集中的每条微博，我们将第一次发布微博的用户作为种子节点并初始化为激活状态。接着从该种子节点出发，基于各个信息传播模型模拟信息随机传播过程。为了取得更为可靠的结果，我们模拟上述随机过程2000次并对结果取平均，得到种子用户发布微博之后，其他所有用户对其转发的概率。

在测试集中，我们知道每个用户是否转发微博，因此可以将每个用户分为两类，正类表示转发，负类表示未转发。那么，对结果的评估可以转换为二分类问题的评估。ROC（Receiver Operating Characteristic）曲线和AUC（Area under the Curve of ROC）经常被用来评估二分类模型的优劣。一个二分类模型，其预测可能有四种结局，可以总结为下图\ref{fig:matrix}：

\begin{figure}[h!]{}
\centering
\includegraphics[width=0.5\textwidth]{figure/chap3/tpfp.png}
\caption{预测结果矩阵}
\label{fig:matrix}
\end{figure}

其中，真阳性率$TPR = TP / (TP + FN)$，假阳性率$FPR = FP / ( FP + TN )$。

在二分类模型预测时，我们需要选定一个阈值$\theta$，如果预测结果$pred > \theta$，则分为正类，否则分为负类。ROC曲线就是就是将选择不同阈值对应的真阳性率和假阳性率绘制成一条曲线，而AUC表示ROC曲线下方面积。AUC值越大，分类效果越好。对于我们的信息传播模型而言，AUC值越大，模型越贴近信息的实际传播结果。

图\ref{fig:roc}展示了不同信息传播模型的ROC曲线，其中IC表示独立传播模型，TIC表示话题传播模型，MIC表示情绪传播模型以及EMIC表示优化情绪传播模型。表\ref{tab-auc}展示了不同信息传播模型的AUC值。

\begin{figure}[h!]{}
\centering
\includegraphics[width=0.5\textwidth]{figure/chap3/roc.png}
\caption{不同信息传播模型的ROC曲线}
\label{fig:roc}
\end{figure}

\begin{table}
    \centering
    \caption{不同信息传播模型的AUC值}
    \label{tab-auc}
    \begin{tabular}{cc}
    \toprule
    模型 & AUC \\
    \midrule 
    优化情绪传播模型 & 0.78736 \\
    情绪传播模型 & 0.75891 \\  
    话题传播模型 & 0.77363  \\
    独立传播模型 & 0.50639 \\
    \bottomrule
    \end{tabular}
\end{table}

\subsubsection{结果分析}

AUC的值为0.5意味着结果和随机猜测一样，模型没有任何预测价值。而独立传播模型的AUC值为0.50639，只比随机猜测好一点，即独立传播模型对于现实的信息传播的抽象能力非常弱，几乎对实际的信息传播过程没有预测性。这是由于独立传播模型建模时，没有考虑信息本身的因素。回顾独立传播模型，该模型的参数个数与边的个数一致，即无论什么信息经过边$e=(v,u)$，其传播概率始终为$p_{v,u}$。这本身不符合人们对信息传播的直观认识，例如对于一条充满低落逃避情绪的微博，心态积极向上的用户转发它的可能性会很低，而心态抑郁的人更倾向于转发它。相反地，对于一条充满高兴情绪的微博，心态积极向上的用户倾向于转发它，而心态抑郁的人转发它的可能性就很低。因此在社交网络中，不同信息的传播能力和传播范围各不相同，针对社交网络的信息传播模型必须考虑到信息本身的因素。我们的实验结果也表明独立传播模型对于不同信息在用户之间传播概率相同的假设显然是错误。

从话题传播模型和情绪传播模型的AUC值可以看出，如果我们在信息传播模型中加入信息本身的因素，无论是话题因素还是情绪因素，都对模型的效果有很大的提升。

话题传播模型假设用户发布的信息带有不同的话题，并将信息对应的话题分布与话题在用户之间的传播概率共同作为模型的参数。由于考虑到不同信息对应不同的传播概率，该模型相对独立传播模型有明显的提升且效果略优于未经优化的情绪传播模型。但是话题传播模型也存在以下明显的不足：
\begin{enumerate}
\item 话题传播模型将话题的个数作为超参数，而论文中没有给出针对不同的应用应该如何选择话题个数，这会给实际的应用带来困扰。
\item 话题传播模型将每条信息对应的话题分布作为模型的参数，一方面增加了参数的个数，在训练样本较少时容易导致过拟合。另一方面，对于训练数据中没有出现过的信息，比如预测用户新发布的一条微博的传播轨迹，该模型的表现会有所下降。
\item 话题传播模型训练完后，话题的分布仅仅是个数值，用户不知道每条信息的话题具体对应什么。因此，该模型的可解释性非常差。
\end{enumerate}

情绪传播模型的结果略差于话题传播模型，这可能是因为话题传播模型参数量更多且训练数据充足造成的。但是，通过我们对缺失边的优化方法，优化情绪传播模型达到了最好的效果，这说明我们对情绪传播的直观假设得到了初步验证。事实上，缺失边的值并不是随意赋值即可。如果对一条真实传播概率较小的边赋值太大，则在预测时可能会将未转发的用户错误标注为转发的用户；相反地，如果对一条真实传播概率较大的边赋值太小，则在预测时可能会将已转发的用户错误标注为未转发的用户。

总的来说，优化情绪传播模型有如下几点优势：
\begin{enumerate}
\item 情绪传播模型相比独立传播模型和话题传播模型，对现实信息传播的过程拟合地最好。
\item 情绪传播模型不需要用户额外指定参数，用户只需要提供信息的历史传播轨迹就可以训练出各种情绪在用户之间的传播概率。
\item 情绪传播模型有较好的解释性，我们可以很容易地知道相同用户对于不同情绪的传播概率情况，方便更进一步地分析。

\end{enumerate}

为了更好地说明情绪传播模型的优势，我们展示一个情绪传播模型的简单应用，分析情绪在网络中的传播。回顾图\ref{fig:mic_edge_probs}和图\ref{fig:emic_edge_probs}，我们发现负面情绪如愤怒和恐惧在传播概率大的部分（图最右侧）占比很高。对于所有的边$(v, u)$以及情绪$c$，我们计算不同情绪对应的边传播概率的平均值，结果在下表\ref{tab-probs-avg}中。可以看出，恐惧情绪的传播概率比其他情绪的传播概率高了约13\%。同时，在情绪传播模型下，携带恐惧情绪的信息更容易传播，即使携带恐惧情绪的微博在新浪微博的网络中占比并不高。

\begin{table}
    \centering
    \caption{不同情绪的平均传播概率}
    \label{tab-probs-avg}
    \begin{tabular}{lcr}
    \toprule
    情绪 & 情绪传播模型 & 优化情绪传播模型 \\
    \midrule 
   	愤怒 & 0.17232 & 0.15926 \\
	厌恶 & 0.17320 & 0.15971 \\
	高兴 & 0.17061 & 0.15310\\
	低落 & 0.16871 & 0.15465\\
	恐惧 & 0.19326 & 0.17522\\
    \bottomrule
    \end{tabular}
\end{table}

为了进一步阐述上述发现的正确性，我们对每种情绪$c$生成了一条假微博$i$，使得：
$$\gamma_i^{c_j} = \begin{cases} 1, & if\ c_j = c \cr 0, &otherwise\end{cases}$$

也就是使得每条微博在一种情绪上的权重为1，其他情绪上的权重为0。这样我们一共得到了五条假微博，其中微博$item1$愤怒情绪权重为1，微博$item2$厌恶情绪权重为1，微博$item3$高兴情绪权重为1，微博$item4$低落情绪权重为1，微博$item5$恐惧情绪权重为1。

之后我们在测试集中随机选择一个节点作为初始节点，将五条微博分别以从该节点出发，模拟信息随机传播过程，传播过程停止时被激活的节点个数即每条微博的影响范围。同样，为了得到一个可靠的结果，我们模拟信息传播过程2000次，并对影响范围取平均，最后得到的结果如下表\ref{tab-if-spread}所示。可以看出，虽然每条微博的影响范围相近，但是恐惧情绪权重为1的微博$item5$仍然取得了最大的影响范围，即携带恐惧的信息容易传播到更大的范围。但是值得注意的是，该结论是在情绪传播模型的框架下得出的，我们没有考虑更多其他的因素例如网络结构等。因此，携带恐惧的信息更容易传播这一结论需要进一步论证。

\begin{table}
    \centering
    \caption{每条微博的平均影响范围}
    \label{tab-if-spread}
    \begin{tabular}{cc}
    \toprule
    微博 & 平均影响范围 \\
    \midrule 
   	item1 & 1.23441 \\
	item2 & 1.25753 \\
	item3 & 1.24619 \\
	item4 & 1.22718 \\
	item5 & 1.27809 \\
    \bottomrule
    \end{tabular}
\end{table}

\section{本章小结}
本章在信息传播中考虑信息所携带的情绪因素，提出了一个基于独立传播模型的情绪传播模型。该模型将信息视为情绪的载体，信息通过情绪在用户之间传播。同时，本文参考独立传播模型中参数估计的方法，给出了使用信息传播历史轨迹来估算情绪传播模型参数的期望最大化算法。

为了解决情绪模型中有些边的情绪传播概率无法学习得到，我们提出了一个优化的方法，使能学习到情绪概率的边达到98\%以上。在微博数据集上的实验结果表明，情绪传播模型比话题传播模型和独立传播模型更具有预测力。
